/*-------------------------------------------------------------------------*/
/**
  @file		graph_func.c
  @author	Renaud Wanschoor
  @date	july 2004
  @version	$Revision: 2.4 $
  @brief	Basic management of the ::GraphType structure.

  tools to handle the ::GraphType datastructure, Initialization, Memomy allocation,
  finalization, Read from a file
  
*/
/*--------------------------------------------------------------------------*/

#include "pagrid.h"

/**
 * \brief Initialize an empty graph structure.
 *
 * dynamically allocate and initialize a graph structure, the returned graph need
 * to be freed using LIBG_Free()
 */
GraphType* LIBG_Init(void) 
{
  GraphType *graph;

  graph = U_malloc(1,GraphType,"LIBG_Init code 1\n");
  graph->wgtflag = 0;
  graph->nvtxs = graph->nedges = -1;
  graph->adjidx = graph->vwgt = graph->adjncy = graph->adjwgt = NULL;
  graph->adjwgtsum = graph->map = graph->match = NULL;
  graph->pro = NULL;
  graph->father = graph->child = NULL;

  MEM_Init(&(graph->mem));
  
  return graph;
}

/**
 * \brief Free a graph structure.
 *
 * \param graph dynamically allocated graph structure
 */
void LIBG_Free(GraphType* graph){
  if(graph == NULL)
    return;

  MEM_Free(&(graph->mem));
  
  U_free("LIBG_Free code 1\n",&graph,LEND);
}

/**
 * \brief Allocate space to store the structure of the graph.
 *
 * Space is allocated according to GraphType::nvtxs and GraphType::nedges
 * \param g dynamically allocated graph, g->nvtxs and g->nedges must be set
 */
void LIBG_Allocate(GraphType* g){
  Mem* mem = &(g->mem);

  MEM_Need(mem, 6*g->nvtxs + 2*g->nedges + 1, int);
  MEM_Allocate(mem);

  g->adjidx    = MEM_Request(mem, g->nvtxs + 1, int);
  g->adjncy    = MEM_Request(mem, g->nedges,    int);
  g->vwgt      = MEM_Request(mem, g->nvtxs,     int); 
  g->adjwgt    = MEM_Request(mem, g->nedges,    int); 
  g->adjwgtsum = MEM_Request(mem, g->nvtxs,     int);
  g->map       = MEM_Request(mem, g->nvtxs,     int);
  g->match     = MEM_Request(mem, g->nvtxs,     int);
  g->pro       = MEM_Request(mem, g->nvtxs,     int);
//  g->checked   = MEM_Request(mem, g->nvtxs,     int);

}

/**
 * \brief Read and store a graph file into a graph structure.
 *
 * fp must point to the begin of the file, the returned structure must be freed
 * by LIBG_Free(). The file format is the same as chaco, metis, jostle, see the 
 * documentation of these tools for more information
 * \param fp file pointer to the beginning of an opened file containing the chaco
 *   formatted structure of the graph
 * \return dynamically allocated graph stucture to be freed by LIBG_Free()
 */
GraphType* LIBG_Read(FILE *fp){
  GraphType *graph;
  
  int i, k, l, fmt, readew, readvw, ncon, edge, ewgt = 0;
  int *adjidx, *adjncy, *vwgt, *adjwgt, *adjwgtsum;
  char *line, *oldstr, *newstr;
  int sum;		
  int degree,maxdegree=0;
  
  /* alloc */
  graph = LIBG_Init();
  line = U_malloc(MAXLINE+1,char,"LIBG_Read code 1\n");

  /* commented lines */
  do { 
    fgets(line, MAXLINE, fp);
  } while (line[0] == '%' && !feof(fp));

  WARNING((feof(fp),"LIBG_Read code 2 : empty file"),NULL);
  
  /* first line */
  fmt = ncon = 0;
  sscanf(line, "%d %d %d %d", &(graph->nvtxs), &(graph->nedges), &fmt, &ncon);

  readew = (fmt%10 > 0);	/*determine readew, if the graph has weights associated with the edges, readew = 1*/
  readvw = ((fmt/10)%10 > 0);		/*determine readvw, if the graph has weights associated with the vertices, readvw = 1*/

  WARNING((fmt>=100,"LIBG_Read code 3 : Cannot read this type of format!"),NULL);
    
  graph->wgtflag = 0;
  if (readew)
    graph->wgtflag += 1;
  if (readvw)
    graph->wgtflag += 2;
  
  if (ncon > 0 && !readvw) {
    printf("------------------------------------------------------------------------------\n");
    printf("***  I detected an error in your input file  ***\n\n");
    printf("You specified ncon=%d, but the fmt parameter does not specify vertex weights\n", ncon);
    printf("Make sure that the fmt parameter is set to either 10 or 11.\n");
    printf("------------------------------------------------------------------------------\n");
    exit(0);
  }
  
  graph->nedges *= 2;
  ncon = graph->ncon = (ncon == 0 ? 1 : ncon);
  
  LIBG_Allocate(graph);

  adjidx    = graph->adjidx;
  adjncy    = graph->adjncy;
  vwgt      = graph->vwgt; 
  adjwgt    = graph->adjwgt; 
  adjwgtsum = graph->adjwgtsum;
  
  
  if (! readvw){	/*If the graph has not weights associated with the vertices, initialize all the weights of vertices to be 1*/
    for (i=0; i<graph->nvtxs; i++)	  graph->vwgt[i] = 1;
  }
  if (! readew){	/*If the graph has not weights associated with the edges, initialize all the weights of edges to be 1*/
    for (i=0; i<graph->nedges; i++)	  graph->adjwgt[i] = 1;
  }
  
  /* Start reading the connectivities of graph file */
  for (adjidx[0]=0, k=0, i=0; i<graph->nvtxs; i++) {
    do {
      fgets(line, MAXLINE, fp);
    } while (line[0] == '%' && !feof(fp));
    sum =0;
    oldstr = line;
    newstr = NULL;

    ERROR((strlen(line) == MAXLINE,"LIBG_Read code 4 : Buffer too small"));
    
    if (readvw) { 	/*If there are more than one weights
			  associated with a vertex, read them*/
      for (l=0; l<ncon; l++) {
	vwgt[i*ncon+l] = (int)strtol(oldstr, &newstr, 10);
	oldstr = newstr;
      }
    }
    
    degree = 0;
    for (;;) {		/*read each edge of vertex i*/
      /*get the label of vertex of a edge*/
      edge = (int)strtol(oldstr, &newstr, 10) - 1;	
      oldstr = newstr;
      
      if (readew) {	/*If there is a weight associated with a 
			  edge, read it*/
	ewgt = (int)strtol(oldstr, &newstr, 10);
	oldstr = newstr;
      }
      
      if (edge < 0)
	break;
      
      adjncy[k] = edge;	/*write the label of vertex of a 
				  edge to adjncy list of edge k*/
      if (readew){	/*If there is a weight associated 
			  with a edge, the adjwgt[k] will 
			  be specified as ewgt, otherwise, 
			  the adjwgt[k] will be assigned as 1*/
	adjwgt[k] = ewgt;
	sum += ewgt;	/*adding adjwgtsum*/
      }
      else{
	sum += 1;	/*adding adjwgtsum*/
      }
      k++;		/*increase the label of vertex with 1*/
      degree++;
    } 
    if(degree>maxdegree)
      maxdegree = degree;
    adjwgtsum[i] = sum;	/*assign value to adjwgtsum[i]*/
    adjidx[i+1] = k;		/*specify the end of index of adjacent vertices. Recall that the adjacent vertices of vertex i is storing in adjidx[i] to adjidx[i+1]*/
  }
  
  graph->maxdeg = maxdegree;
  if (k != graph->nedges) {
    printf("------------------------------------------------------------------------------\n");
    printf("***  I detected an error in your input file  ***\n\n");
    printf("In the first line of the file, you specified that the graph contained\n%d edges. However, I only found %d edges in the file.\n", graph->nedges/2, k/2);
    if (2*k == graph->nedges) {
      printf("\n *> I detected that you specified twice the number of edges that you have in\n");
      printf("    the file. Remember that the number of edges specified in the first line\n");
      printf("    counts each edge between vertices v and u only once.\n\n");
    }
    printf("Please specify the correct number of edges in the first line of the file.\n");
    printf("------------------------------------------------------------------------------\n");
    exit(0);
  }

  U_free("LIBG_Read code 5\n",&line,LEND);
  return graph;
}
